/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance1 = function(word1, word2) {
    let n = word1.length;
    let m = word2.length;
    if ( n === 0 && m !== 0)
        return m;
    if ( n !== 0 && m === 0)
        return n;
    if ( n === 0 && m === 0)
        return 0;
    let lu = word1[n-1] === word2[m-1] ? 0 : 1;
    let m1 = minDistance(word1.slice(0, n-1), word2) + 1;
    let m2 = minDistance(word1, word2.slice(0, m-1)) + 1;
    let m3 = minDistance(word1.slice(0, n-1), word2.slice(0, m-1)) + lu;
    return Math.min(m1, m2, m3);
};
var minDistance = function(word1, word2) {
    let n = word1.length;
    let m = word2.length;
    if( n * m === 0)
        return n + m;  // 有一个为0，则返回另一个的长度。

    const dp = new Array(n+1).fill(0).map(()=>Array(m+1).fill(0));
    for (let i = 0; i <= n ; i++) {
        for (let j = 0; j <= m ; j++) {
            if ( i === 0 && j !== 0)
                dp[i][j] = j;
            else if ( i !== 0 && j === 0)
                dp[i][j] = i;
            else if ( i!==0 && j !== 0) {
                let lu = word1[i-1] === word2[j-1] ? 0 : 1;
                dp[i][j] = Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + lu);
            }
        }
    }
    return dp[n][m];
}
console.log(minDistance("intention", "execution"));